package leetcode.top100;

import java.util.Arrays;

/**
 * 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
 * <p>
 * 现在要求你戳破所有的气球。每当你戳破一个气球 i 时，
 * <p>
 * 你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 
 * <p>
 * 这里的 left 和 right 代表和 i 相邻的两个气球的序号。
 * <p>
 * 注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
 * <p>
 * 求所能获得硬币的最大数量。
 * <p>
 * 说明:
 * <p>
 * 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
 * 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
 * 示例:
 * <p>
 * 输入: [3,1,5,8]
 * 输出: 167
 * 解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
 *      coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
 *
 * @date 2020/5/23 22:31
 */
public class Code312_戳气球_DP {
    public static void main(String[] args) {
        int[] nums = {7, 9, 8, 0, 7, 1, 3, 5, 5, 2, 3, 3};
        System.out.println(new Code312_戳气球_DP().maxCoins(nums));
    }

    /**
     * 方式1：暴力回溯
     * 对数组从第一个位置一直到最后一个位置， 枚举
     */
    int res = Integer.MIN_VALUE;

    /* 输入一组气球，返回戳破它们获得的最大分数 */
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        backtrack(nums, 0);
        return res;
    }

    /* 回溯算法的伪码解法 */
    private void backtrack(int[] nums, int score) {
        if (nums == null) {
            res = Math.max(res, score);
            return;
        }
        //对数组进行枚举，0号左侧和最后一号右侧注意特殊处理
        for (int i = 0; i < nums.length; i++) {
            int left = i == 0 ? 1 : nums[i - 1];
            int right = i == nums.length - 1 ? 1 : nums[i + 1];
            int point = left * nums[i] * right;

            int[] copy = Arrays.copyOf(nums, nums.length);
            // 做选择
//            在 nums 中删除元素 nums[i]
            nums = deleteNumsIndex(nums, i);
            // 递归回溯
            backtrack(nums, point + score);
            // 撤销选择
//            将 index 还原到 nums[i]
            nums = copy;
        }

    }

    private int[] deleteNumsIndex(int[] nums, int index) {
        if (nums.length == 1) return null;
        int[] res = new int[nums.length - 1];
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (j != index)
                res[i++] = nums[j];
        }
        return res;
    }

    /**
     * 方式2：动态规划
     * dp[i][j] = x 表示，
     * 戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最高分数为 x。
     * dp[i][j] = dp[i][k] + dp[k][j]
     * + points[i]*points[k]*points[j]
     * 你不是要最后戳破气球 k 吗？那得先把开区间 (i, k) 的气球都戳破，
     * 再把开区间 (k, j) 的气球都戳破；最后剩下的气球 k，相邻的就是气球 i 和气球 j，
     * 这时候戳破 k 的话得到的分数就是 points[i]*points[k]*points[j]
     */
    private int maxCoins2(int[] nums) {
        if(nums == null || nums.length == 0)return 0;
        int n = nums.length;
        // 添加两侧的虚拟气球
        int[] points = new int[n + 2];
        points[0] = points[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            points[i] = nums[i - 1];
        }
        // base case 已经都被初始化为 0
        int[][] dp = new int[n + 2][n + 2];
        // 开始状态转移
        // i 应该从下往上
        for (int i = n; i >= 0; i--) {
            // j 应该从左往右
            for (int j = i + 1; j < n + 2; j++) {
                // 最后戳破的气球是哪个？
                for (int k = i + 1; k < j; k++) {
                    // 择优做选择
                    dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]
                    );
                }
            }
        }
        return dp[0][n + 1];
    }

}
